High-Performance Parallel Computing

CS598 :: Fall 2026

Class Time: Wednesday/Friday 12:30-1:45pm [Catalog]
Class Location: 1304 Siebel Center for Comp. Science
Instructor: Paul Fischer
Office Hours: 4320 Siebel, Thu. 3:00-4:30 or by appointment
About the Course
Lectures
Quizzes
Homework
Midterm Project
Final Project

About the Course

This course focuses on high-performance distributed-memory parallelism for scientific computing. We will address (CPU) performance at the node level, weak- and strong-parallel scaling, communication-minimal and low-latency data exchange strategies for a variety of algorithms (direct linear solves for full and banded systems, iterative solvers, multidimensional FFTs, hash tables, etc.). This is a hands-on course with multiple programming exercises in C. Students are expected to be proficient in C or Fortran and in unix or variants such as linux. Students will learn how to design and test distributed-memory parallel algorithms, how to use MPI at scale, and how to optimize single-node performance.

List of Topics

Introduction
Single-Node Performance
- Pipelining / vectorization
- Avoiding loop clutter
- Identifying vector dependencies
- Importance of unit-stride addressing
- BLAS1, BLAS2, and BLAS3 (HW1)
Communication Performance
- Ping-pong benchmark
  - Nonblocking MPI
  - Latency (α)
  - Inverse bandwidth (β)
- On-node vs. off-node communication performance
- Scalable vector reduction
- Distributed prefix (running) sum
Fast Poisson Solver
- Distributed transpose
  - Two-dimensional all-to-all transpose
- Parallel FFT-based Poisson solver
- Complexity analysis
- Extension to three dimensions
- Three-dimensional Fast Poisson solver
Direct Solvers
- Direct matrix factorization
  - BLAS-1 implementation
  - Partial pivoting
  - Blocked BLAS-3 implementation
- Parallel banded solvers
  - Tridiagonal systems
  - Extension to bandwidth b ≪ n
  - Complexity analysis
Communication Algorithms
- Crystal router
  - Arbitrary processor counts
  - Communication traffic analysis
- Gather-scatter operations (gslib)
  - Planar averaging
  - Finite-element assembly
  - User-defined gather-scatter operations
Domain Decomposition
- Domain Decomposition I
  - Jacobi iteration
  - Halo exchange
  - Strong scaling
  - Parallel efficiency
- Domain Decomposition II
  - Conjugate Gradient
  - Strong scaling
  - s-step methods
- Domain Decomposition III
  - Multigrid
  - Coarse-grid solvers
- Three-dimensional geometric multigrid
- Graph partitioning
Other Parallel Algorithms
- Parallel sorting
  - Radix sort
  - Bitonic sort
  - Bucket sort
  - Communication-aware load balancing
For each algorithm, we consider Performance and Performance Modeling
- Computational complexity
- Communication complexity
- O(n), O(n/P), O(P), O(log P)
- Performance models
- Measured vs. predicted performance
- Cache-aware algorithms
- BLAS optimization
- Expected performance bounds
- Estimating n_{0.8}
- Time-to-solution models
  - Dependence on n/P
  - Dependence on machine characteristics

Prerequisites

The expectation is that you have had a course in numerical methods (like CS450) covering numerical linear algebra and perhaps the basics of numerical methods for differential equations or other disciplines. If you do not have this background, please check with the instructor.

You should have skills in some programming language, preferably a compiled language like C or Fortran. In addition, you should have familiarity with linux/unix, including the use of an editor or should pick up basics in this class.

Expected work

The course involves ~ 7 to 10 assignments along with short midterm and final project presentations based on material developed over the semester. There is also a strong participation grade based on quizzes, handouts, and other in-class tasks. The tentative grade breakdown is:

Work in teams of two for the Homework and Projects.

Quizzes, in-class work 10
Homework 70
Midterm Project 10
Final Project 10

Course assignments will be in C.

References

Category	References
Fundamental concurrent scientific-computing algorithms	van_de_velde_concurrent_sci_comp.pdf
Strong-scaling studies	aiaa_2015_strong_scale.pdf bp_paper.pdf lusk_million_2009.pdf sc17.slow-mpi.pdf
Communication strategies	bienz_mpi_2023.pdf petsc_mpi_2021.pdf victor_eijkhout_mpi_perf_2018.pdf david_scott_all_to_all_91.pdf
Single-node computer architecture	hennesy_patterson.pdf
Rank undersubscription	undersubscribe_2024.pdf

Lectures

Lecture	Date	Topic
	08-26	About the course, intro to message passing lec01.pdf hw1.pdf msg_passing_files.tar scripts.tar hw1_matl.tar
	08-28	Scaling analysis example; intro to single-core performance; first MPI code lec02.pdf hpc.pdf ring.c

Quizzes

Homework

Homework 1, Due: Wednesday, Sep. 2, 8 pm

Guidelines and files:

Work in Pairs There should be one write-up for each pair of students (but submit a copy under each student's name).
Homework Submission: All homework must be typeset using LaTeX. Use the provided templates to get started, available at homework-netid-N.tex
Figures: Make sure all figures are clearly labeled with axes, titles, legends, and captions. Each figure must be referenced and discussed within your text for full credit. Be sure to use logscales, where appropriate.
Originality: Your submitted code and figures must be your own. If you use someone else's work, you must cite it.
Code-Based Problems: Code in C. This will allow us to compare performance/issues, etc. (It's not a race.) To receive points for problems involving code, your code must reproduce the reported figures and data. No points will be awarded for the Codes that do not generate the reported results.
Debugging Efforts: If you encounter issues that prevent your code from working as expected, detailed descriptions of your debugging attempts can earn you partial credit.

Midterm / Final Projects

Midterm and final exams will be in the form of project presentations. Details to follow.